package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

class PartitionList {
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode partition(ListNode head, int x) {
            if (head==null)return null;
            ListNode small = new ListNode(0);
            ListNode big = new ListNode(0);
            ListNode dummyBig = big;
            ListNode dummySmall= small;

            while (head != null) {
                if (head.val < x){
                    small.next = head;
                    head = head.next;
                    small.next.next=null;
                    small = small.next;
                } else {
                    big.next = head;

                    head = head.next;
                    big.next.next = null;
                    big = big.next;
                }
            }
            small.next = dummyBig.next;
            return dummySmall.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
}